// https://www.lintcode.com/problem/word-break/my-submissions
// 107. Word Break
// Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

// Example
// Given s = "lintcode", dict = ["lint", "code"].

// Return true because "lintcode" can be break as "lint code".



class Solution {
public:
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
     
    // Memory Limit Exceeded
    // bool wordBreak(string &s, unordered_set<string> &dict) {
    //     map<string, bool> record;
    //     return dfs(s, dict, record);
    // }
    // bool dfs(string s, unordered_set<string> dict, map<string, bool> record) 
    // {
    //     if (dict.size() == 0)
    //     {
    //         return s == "";
    //     }
    //     if (record.find(s) != record.end())
    //     {
    //         return record[s];
    //     }
    //     for (int i = 1; i < s.length() + 1; ++i)
    //     {
    //         if (dict.find(s.substr(0, i)) != dict.end()) 
    //         {
    //             if (i == s.length() || dfs(s.substr(i, s.length()), dict, record))
    //             {
    //                 record[s] = true;
    //                 return true;
    //             }
    //         }
    //     }
    //     record[s] = false;
    //     return false;
    // }
    
    
    
    bool wordBreak(string &s, unordered_set<string> &dict) {
        int maxLen = 0;
        for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it)
        {
            maxLen = (*it).length() > maxLen ? (*it).length() : maxLen;            
        }
        bool *canSegment = new bool[s.length() + 1];
        canSegment[0] = true;
        for (int i = 1; i <= s.length(); ++i)
        {
            canSegment[i] = false;
            for (int j = 1; j <= maxLen && j <= i; j++)
            {
                if (!canSegment[i - j])
                {
                    continue;
                }
                if (dict.find(s.substr(i - j, j)) != dict.end())
                {
                    canSegment[i] = true;
                    break;
                }
            }
        }
        return canSegment[s.length()];
    }
    
};